public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        int m = (int)Math.sqrt(n);
        for(int i = 1; i <= n; i++){
            dp[i] = 0x3f3f3f3f;
        }
        for(int i = 1; i <= m; i++){
            for(int j = i * i; j <= n; j++){
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];

    }
}
